/*!
 Temelia - Splay tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/splay_tree.h"
#include "include/common.h"
#include <stdlib.h>

static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
		int compare(void *x, void *y, void *context), void *context);

splay_tree_t splay_tree_new(void *key)
{
	return _binary_tree_new(key);
}

void splay_tree_delete_node(splay_tree_t splay_tree)
{
	_ASSERT(splay_tree, ==, NULL, NULL_POINTER,);

	_delete(splay_tree);
}

void splay_tree_delete(splay_tree_t splay_tree)
{
	_ASSERT(splay_tree, ==, NULL, NULL_POINTER,);

	splay_tree_delete(_binary_tree_get_left_child(splay_tree));
	splay_tree_delete(_binary_tree_get_right_child(splay_tree));
	splay_tree_delete_node(splay_tree);
}

int splay_tree_compare_trees(splay_tree_t splay_tree1,
		splay_tree_t splay_tree2, int compare(void *x, void *y, void *context),
		void *context)
{
	return _binary_tree_compare_trees(splay_tree1, splay_tree2, compare,
			context);
}

int splay_tree_is_empty(splay_tree_t splay_tree)
{
	return (_binary_tree_get_parent(splay_tree) == NULL)
			&& (_binary_tree_get_left_child(splay_tree) == NULL)
			&& (_binary_tree_get_right_child(splay_tree) == NULL)
			&& (_binary_tree_get_key(splay_tree) == NULL);
}

int splay_tree_is_leaf(splay_tree_t splay_tree)
{
	return _binary_tree_leaf(splay_tree);
}

splay_tree_t splay_tree_get_root(splay_tree_t splay_tree)
{
	return _binary_tree_get_root(splay_tree);
}

void *splay_tree_get_key(splay_tree_t splay_tree)
{
	void *node;

	_ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);

	node = _binary_tree_get_key(splay_tree);

	return node;
}

int splay_tree_get_size(splay_tree_t splay_tree)
{
	return _binary_tree_get_size(splay_tree);
}

splay_tree_t splay_tree_get_parent(splay_tree_t splay_tree)
{
	return _binary_tree_get_parent(splay_tree);
}

splay_tree_t splay_tree_get_left_child(splay_tree_t splay_tree)
{
	return _binary_tree_get_left_child(splay_tree);
}

splay_tree_t splay_tree_get_right_child(splay_tree_t splay_tree)
{
	return _binary_tree_get_right_child(splay_tree);
}

int splay_tree_get_height(splay_tree_t splay_tree)
{
	return _binary_tree_get_height(splay_tree);
}

int splay_tree_get_depth(splay_tree_t splay_tree)
{
	return _binary_tree_get_depth(splay_tree);
}

splay_tree_t splay_tree_search(splay_tree_t splay_tree, void *key, int compare(
		void *x, void *y, void *context), void *context)
{
	return _binary_search_tree_search(splay_tree, key, compare, context);
}

splay_tree_t splay_tree_insert(splay_tree_t _splay_tree, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	splay_tree_t new;

	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	new = splay_tree_new(key);

	if (_splay_tree == NULL)
	{
		new->left = new->right = new->parent = NULL;
		return new;
	}

	_splay_tree = _splay_tree_splay(key, _splay_tree, compare, context);

	if (compare(key, _splay_tree->key, context) < 0)
	{
		new->left = _splay_tree->left;
		new->right = _splay_tree;
		_splay_tree->left = NULL;

		if (new->left)
			new->left->parent = new;
		if (new->right)
			new->right->parent = new;

		return new;
	}
	else if (compare(key, _splay_tree->key, context) > 0)
	{
		new->right = _splay_tree->right;
		new->left = _splay_tree;
		_splay_tree->right = NULL;

		if (new->left)
			new->left->parent = new;
		if (new->right)
			new->right->parent = new;

		return new;
	}
	else
	{
		splay_tree_delete_node(new);
		return _splay_tree;
	}

	return NULL;
}

splay_tree_t splay_tree_remove(splay_tree_t splay_tree, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	splay_tree_t x = NULL;

	LOGGER("[splay tree remove] tree %p, key %p, compare %p, context %p\n",
			splay_tree, key, compare, context);

	_ASSERT(splay_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	splay_tree = _splay_tree_splay(key, splay_tree, compare, context);

	if (compare(key, splay_tree->key, context) == 0)
	{
		if (splay_tree->left == NULL)
			x = splay_tree->right;
		else
		{
			x = _splay_tree_splay(key, splay_tree->left, compare, context);
			x->right = splay_tree->right;
			if (x->right)
				x->right->parent = x;
		}

		splay_tree_delete_node(splay_tree);
		return x;
	}
	return splay_tree;
}

splay_tree_t splay_tree_get_min(splay_tree_t splay_tree)
{
	return _binary_search_tree_get_min(splay_tree);
}

splay_tree_t splay_tree_get_max(splay_tree_t splay_tree)
{
	return _binary_search_tree_get_max(splay_tree);
}

void splay_tree_preorder(splay_tree_t splay_tree, void key_handler(void *x,
		void *context), void *context)
{
	_binary_tree_preorder(splay_tree, key_handler, context);
}

void splay_tree_inorder(splay_tree_t splay_tree, void key_handler(void *x,
		void *context), void *context)
{
	_binary_tree_inorder(splay_tree, key_handler, context);
}

void splay_tree_reverse_inorder(splay_tree_t splay_tree, void key_handler(
		void *x, void *context), void *context)
{
	_binary_tree_reverse_inorder(splay_tree, key_handler, context);
}

void splay_tree_postorder(splay_tree_t splay_tree, void key_handler(void *x,
		void *context), void *context)
{
	_binary_tree_postorder(splay_tree, key_handler, context);
}

void splay_tree_level_order(splay_tree_t splay_tree, void key_handler(void *x,
		void *context), void *context)
{
	_binary_tree_level_order(splay_tree, key_handler, context);
}

void splay_tree_show_indented(splay_tree_t splay_tree, void key_handler(
		void *x, int level, void *context), void *context)
{
	_binary_tree_show_indented(splay_tree, key_handler, context, 0);
}

static splay_tree_t _splay_tree_splay(void *key, splay_tree_t tree,
		int compare(void *x, void *y, void *context), void *context)
{
	splay_tree_t left, right;
	struct _bt_node_t new_node;
	int comp;

	_ASSERT(tree, ==, NULL, NULL_POINTER, NULL);

	new_node.left = new_node.right = NULL;
	left = right = &new_node;

	for (;;)
	{
		comp = compare(key, splay_tree_get_key(tree), context);

		if (comp < 0)
		{
			if (_binary_tree_get_left_child(tree) == NULL)
				break;
			if (compare(key, _binary_tree_get_key(_binary_tree_get_left_child(
					tree)), context) < 0)
			{
				tree = _self_balanced_binary_search_tree_rotate_right(tree);

				if (_binary_tree_get_left_child(tree) == NULL)
					break;
			}

			_binary_tree_set_left_child(right, tree);
			right = tree;
			tree = _binary_tree_get_left_child(tree);
		}
		else if (comp > 0)
		{
			if (_binary_tree_get_right_child(tree) == NULL)
				break;

			if (compare(key, _binary_tree_get_key(_binary_tree_get_right_child(
					tree)), context) > 0)
			{
				tree = _self_balanced_binary_search_tree_rotate_left(tree);

				if (_binary_tree_get_right_child(tree) == NULL)
					break;
			}

			_binary_tree_set_right_child(left, tree);
			left = tree;
			tree = _binary_tree_get_right_child(tree);
		}
		else
			break;
	}

	_binary_tree_set_right_child(left, _binary_tree_get_left_child(tree));
	_binary_tree_set_left_child(right, _binary_tree_get_right_child(tree));

	_binary_tree_set_left_child(tree, new_node.right);
	if (tree->right)
		tree->right->parent = tree;

	_binary_tree_set_right_child(tree, new_node.left);
	if (tree->left)
		tree->left->parent = tree;

	tree->parent = NULL;

	return tree;
}
